//
//  SqList.c
//  DataStruct
//
//  Created by vase on 2022/2/23.
//  线性表相关

#include "SqList.h"

Sqlist initSqlist(int length) {
    Sqlist* list = (Sqlist *)malloc(sizeof(Sqlist));
    list->length = length;
    list->offset = 0;
    list->list = (ElementType *)malloc(sizeof(ElementType)*length);
    return *list;
}

int add(Sqlist *list, int value) {
    if (list->offset >= list->length) {
        return Sqlist_Error;
    }
    return list->list[list->offset++] = value; //赋值并使得偏移量递增
}

int insert(Sqlist *list, int index, int value) {
    if ((index < 0 || index > list->offset) && list->offset+1<list->length) {
        return Sqlist_Error; //数组越界
    }
    //将后续元素统一移动一定距离
    int tail = list->offset-1;
    while (tail >= index) {
        list->list[tail+1] = list->list[tail];
        tail--;
    }
    list->offset++; //顺序表偏移量加1
    return list->list[index] = value; //赋值
}

int removeMin(Sqlist *list) {
    if (list->offset == 0) {
        return Sqlist_Error; //顺序表长度为零则结束函数
    }
    int min = list->list[0], index = 0; //初始化数据
    for (int i = 0; i < list->offset; i++) {  //循环搜索
        if (list->list[i] < min) {
            min = list->list[i];
            index = i;
        }
    }
    //找到最小值以后进行替换
    list->list[index] = list->list[--list->offset];
    return min;
}

void showSequence(Sqlist *list) {
    for (int i = 0; i < list->offset; i++) {
        printf("%d ", list->list[i]);
    }
    printf("\n");
}

void reserve(Sqlist *list) {
    int head = 0, tail = list->offset-1; //设置头尾指针
    while (head < tail) {
        //交换两端元素
        int t = list->list[head];
        list->list[head] = list->list[tail];
        list->list[tail] = t;
        //指针移动
        head++;
        tail--;
    }
}

//反转指定范围内的数组
void reserveRange(Sqlist *list, int head, int tail) {
    while (head < tail) {
        //交换两端元素
        int t = list->list[head];
        list->list[head] = list->list[tail];
        list->list[tail] = t;
        //指针移动
        head++;
        tail--;
    }
}

/** 整体思路是从后面开始往前删除*/
int removeRepeate(Sqlist *list, int value) {
    int tail = list->offset-1;  //定义一个尾部指针
    while (tail >= 0) {
        if (list->list[tail] == value) {
            //如果遇到要删除的元素，那就把其后的元素整体前移
            for (int i = tail+1; i < list->offset; i++) {
                list->list[i-1] = list->list[i];
            }
            list->offset--; //删除元素完毕，偏移量减1
        }
        tail--;
    }
    return 1;
}

/** 整体思路同上个方法，只不过删除元素的条件改变*/
int removeRange(Sqlist *list, int s, int t) {
    if (s >= t || list->offset==0) {
        return Sqlist_Error;
    }
    int tail = list->offset-1;  //定义一个尾部指针
    while (tail >= 0) {
        if (list->list[tail]>=s && list->list[tail]<=t) {
            //如果遇到要删除的元素，那就把其后的元素整体前移
            for (int i = tail+1; i < list->offset; i++) {
                list->list[i-1] = list->list[i];
            }
            list->offset--; //删除元素完毕，偏移量减1
        }
        tail--;
    }
    return 1;
}

/** 有序数组去重，则重复元素必定相邻，依旧从后往前遍历清除*/
int removeToOnly(Sqlist *list) {
    int tail = list->offset-1;  //定义一个尾部指针
    while (tail > 0) {
        if (list->list[tail-1] == list->list[tail]) { //发现重复元素
            int i = tail;
            while (list->list[i-1] == list->list[i]) { //反复确认所有重复元素
                i--;
            }
            int nextStep = i;
            //去重--将后面的不重复元素，向前移动一定的位置
            for (int j = tail; j < list->offset; j++) {
                list->list[i++] = list->list[j];
            }
            //修改顺序表的偏移量，注意不要在循环遍历的时候修改offset，不够优雅
            list->offset = list->offset - (tail-nextStep);
            //重置指针位置
            tail = nextStep;
            continue;
        }
        tail--;
    }
    return 1;
}

/** 冒泡排序*/
void sort(Sqlist *list) {
    for (int i = 0; i < list->offset-1; i++) {
        for (int j = (i+1); j < list->offset; j++) {
            if (list->list[i] > list->list[j]) {
                int t = list->list[i];
                list->list[i] = list->list[j];
                list->list[j] = t;
            }
        }
    }
}

/** 你拍一，我拍一*/
Sqlist merge(Sqlist *list1, Sqlist* list2) {
    //初始化结果顺序表
    Sqlist *merge = (Sqlist *)malloc(sizeof(Sqlist));
    merge->length = list1->offset+list2->offset;
    merge->offset = merge->length;
    merge->list = (int *)malloc(sizeof(ElementType)*merge->offset);
    int index1 = 0, index2 = 0; //定义两个指针分别指向两个顺序表
    int i = 0; //合并后顺序表的下标
    while (index1 < list1->offset && index2 < list2->offset) {
        //将较小的元素赋予合并后的顺序表，并移动对应指针
        merge->list[i++] = list1->list[index1] < list2->list[index2] ? list1->list[index1++] : list2->list[index2++];
    }
    //如果第一个有序表还有剩余
    if (index1 < list1->offset) {
        //将剩余的元素，全部加到合并后顺序表的尾巴上
        while (index1 < list1->offset) {
            merge->list[i++] = list1->list[index1++];
        }
    }
    if (index2 < list2->offset) {
        //将剩余的元素，全部加到合并后顺序表的尾巴上
        while (index2 < list2->offset) {
            merge->list[i++] = list2->list[index2++];
        }
    }
    return *merge;
}

/** 先将整个数组反转，然后将两个顺序表范围内的元素反转*/
void adjustLocation(Sqlist *list, int m ,int n) {
    reserveRange(list, 0, m+n-1); //整个数组层面的反转
    reserveRange(list, 0, n-1); //反转前半部分
    reserveRange(list, n, m+n-1); //反转后半部分
}

/** 二分查找到大于等于指定元素的第一个元素，然后再交换或插入*/
void fastSearch(Sqlist *list, int value) {
    int head = 0, tail = list->offset-1; //指定两端指针
    int mid = 0;
    while (head <= tail) {
        mid = (tail+head)/2;
        if (list->list[mid] > value) {
            tail = mid - 1;
        }else if(list->list[mid] < value) {
            head = mid + 1;
        }else {
            //查找到了对应的元素，与其后继元素完成替换
            if (mid + 1 < list->offset) {
                int t = list->list[mid];
                list->list[mid] = list->list[mid+1];
                list->list[mid+1] = t;
            }
            return ;
        }
    }
    //如果走到这里仍然没有结束程序，那么就说明只能把对应元素插入到合适的位置
    insert(list, head, value);
}

/** 流动起来*/
void leftShift(Sqlist *list, int p) {
//    for (int i = list->offset-p-1; i >= 0; i--) {
//        int step = (i+p)%list->offset;
//        if ((i+p)/list->offset==0) {
//            int t =  list->list[step];
//            list->list[step] = list->list[i];
//            list->list[i] = t;
//        }else {
//            int value = list->list[i];
//            for (int j = i-1; j>=0; j--) {
//                list->list[j+1] = list->list[j];
//            }
//            list->list[step] = value;
//        }
//    }
    //确实牛逼，借用之前的结论ab-->ba
    reserveRange(list, 0, list->offset-1);
    reserveRange(list, 0, list->offset-p-1);
    reserveRange(list, list->offset-p, list->offset-1);
}

int middle(Sqlist *list1, Sqlist *list2) {
    int midNum = (list1->offset+list2->offset)/2;
    int index1 = 0, index2 = 0, now = -1;
    while (index1 < list1->offset || index2 < list2->offset) {
        now = list1->list[index1] < list2->list[index2] ? list1->list[index1++] : list2->list[index2++];
        midNum--;
        if (midNum == 0) {
            return now;
        }
    }
    if (index1 < list1->offset) {
        while (index1 < list1->offset) {
            now = list1->list[index1++];
            midNum--;
            if (midNum == 0) {
                return now;
            }
        }
    }
    if (index2 < list2->offset) {
        while (index2 < list2->offset) {
            now = list2->list[index2++];
            midNum--;
            if (midNum == 0) {
                return now;
            }
        }
    }
    return now;
}

/** 记录每个元素出现的次数，如果是高级语言直接上map就行啦*/
int domain(Sqlist *list) {
    
    return 0;
}

/** 最小正整数只和最大正数和最小正数有关*/
int minNum(Sqlist *list) {
    int min = list->list[0], max = list->list[0]; //定义初始值
    //遍历寻找最大值和最小值
    for (int i = 0; i < list->offset; i++) {
        if (list->list[i] > max) {
            max = list->list[i];
        }
        if (list->list[i]>0 && list->list[i] < min) {
            min = list->list[i];
        }
    }
    if (min > 1) {
        return min-1;
    }else if(max <= 0) {
        return 1;
    }else {
        return max+1;
    }
}
